//class Solution {
//public:
//    int add(int a, int b) {
//        long long ret = a, addBit = b;
//        while (addBit)
//        {
//            int tmp = ret;
//            ret = tmp ^ addBit;
//            addBit = (tmp & addBit) << 1;
//        }
//        return ret;
//    }
//};


class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        unordered_map<string, bool> hash;
        for (auto& str : dictionary)
            hash[str] = true;
        int n = sentence.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++)
        {
            dp[i] = dp[i - 1] + 1;
            for (int j = i; j >= 1; j--)
            {
                string tmp = sentence.substr(j - 1, i - j + 1);
                if (hash.count(tmp))
                    dp[i] = min(dp[i], dp[j - 1]);
            }
        }
        return (dp[n] == 0x3f3f3f3f) ? n : dp[n];
    }
};